Computers are designed to execute computer programs written in a format understood by the computer, such as machine code. However, programmers typically do not write computer programs in machine code. Instead, programmers typically write computer programs using human readable programming languages (e.g., JAVA™ (JAVA™ is a trademark of Sun Microsystems, Inc.), C, C++, C#, etc.). The resulting computer program is then compiled to generate a computer program in a format understood by the computer.
The process of compilation is performed by a compiler. Compilers typically use the source code (e.g., computer program written in a human readable programming language) as input and generate object code, which is able to be transformed by another program into an executable (e.g., a format understood by the computer). When compiling a program, the compiler may perform various steps for optimization of the object code. For example, the compiler may optimize the object code for memory usage, execution efficiency, and/or the target computer system upon which the object code will execute.
For example, consider the scenario in which a program has a two-dimensional array of integers. Further, in the example, the source code of the program includes instructions for adding “1” to each integer in the two-dimensional array. Specifically, the source code may include an inner loop that iterates through the rows of the two-dimensional array, and an outer loop that iterates through the columns of the two-dimensional array. In order to optimize the program for memory locality when the array is stored with elements in the same column adjacent in memory (i.e., column major order), the compiler may change the order of the two loops, such that the inner loop iterates through the columns and the outer loop iterates through the rows of the two-dimensional array. The compiler may also perform loop unrolling by removing the inner and outer loop and specifying each of the instructions of the loop. Thus, the resulting executable may take less time to execute than an executable created if the source code were transformed directly (i.e., without optimization).
Compiler optimization eases the development of a program. In particular, a programmer may develop source code without worrying about execution efficiency or memory usage or the particular computer system that will execute the compiled source code and allow the compiler to perform appropriate optimizations. Therefore, improvements in compiler optimizations techniques are desirable.